#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MEMORYLENGTH 5

// print the page array
void printPageArray(int *array, int length) {
    for (size_t i = 0; i < length; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
}

//print the page matrix
void printMateix(int array[MEMORYLENGTH][MEMORYLENGTH]) {
    for (size_t i = 0; i < MEMORYLENGTH; i++) {
        printf("\t");
        for (int j = 0; j < MEMORYLENGTH; ++j) {
            printf("%d ", array[i][j]);
        }
        puts("");
    }
    printf("\n");
}

void queuePush(int page, int *count, int *array, int arrayLength) {
    for (size_t i = 0; i < *count; i++) {
        if (array[i] == page) {
            return;
        }
    }

    if (arrayLength <= 0) {
        printf("The array length is null! \n");
        return;
    }

    if (*count != arrayLength) {
        for (int i = arrayLength - 1; i > 0; --i) {
            array[i] = array[i - 1];
        }
        array[0] = page;
        (*count)++;
    } else {
        if (arrayLength == 1) {
            array[0] = page;
            return;
        }

        for (int i = arrayLength - 1; i >= 1; --i) {
            array[i] = array[i - 1];
        }
        array[0] = page;
    }
}

void stackPush(int page, int *count, int *array, int arrayLength) {
    for (size_t i = 0; i < *count; i++) {
        if (array[i] == page) {
            if (i == (*count) - 1) {
                return;
            } else {
                for (int j = i; j < (*count) - 1; ++j) {
                    array[j] = array[j + 1];
                }
                array[(*count) - 1] = page;
            }
        }
    }

    if (arrayLength <= 0) {
        printf("The array length is null! \n");
        return;
    }
    if (*count == arrayLength) {
        array[0] = page;
    } else {
        array[*count] = page;
        (*count)++;
    }
}

void FIFO(int *inputPage, int inputPageLength, int *output, int outputLength) {
    printf("FIFO :\n");
    int count = 0;
    for (int i = 0; i < inputPageLength; ++i) {
        queuePush(inputPage[i], &count, output, outputLength);
        printPageArray(output, outputLength);
    }
}

void matrixPush(int page, int *count, int *array, int arrayLength, int mat[MEMORYLENGTH][MEMORYLENGTH]) {

    for (size_t i = 0; i < *count; i++) {
        if (array[i] == page) {
            for (int j = 0; j < MEMORYLENGTH; ++j) {
                mat[i][j] = 1;
            }
            for (int j = 0; j < MEMORYLENGTH; ++j) {
                mat[j][i] = 0;
            }
            return;
        }
    }

    if (arrayLength <= 0) {
        printf("array length is null! \n");
        return;
    }

    if (*count == arrayLength) {
        int sum = RAND_MAX;
        int sumIndex = 0;
        for (size_t i = 0; i < MEMORYLENGTH; i++) {
            int tempsum = 0;
            for (size_t j = 0; j < MEMORYLENGTH; j++) {
                tempsum += mat[i][j];
            }

            if (tempsum < sum) {
                sum = tempsum;
                sumIndex = i;
            }
        }

        array[sumIndex] = page;

        for (int j = 0; j < MEMORYLENGTH; ++j) {
            mat[sumIndex][j] = 1;
        }
        for (int j = 0; j < MEMORYLENGTH; ++j) {
            mat[j][sumIndex] = 0;
        }
    } else {
        array[*count] = page;
        for (int j = 0; j < MEMORYLENGTH; ++j) {
            mat[*count][j] = 1;
        }
        for (int j = 0; j < MEMORYLENGTH; ++j) {
            mat[j][*count] = 0;
        }
        (*count)++;
    }
}

void LRUwithStack(int *inputPage, int inputPageLength, int *output, int outputLength) {

    printf("LRUwithStack :\n");
    int count = 0;
    for (int i = 0; i < inputPageLength; ++i) {
        stackPush(inputPage[i], &count, output, outputLength);
        printPageArray(output, outputLength);
    }
}

void LRUwithMatrix(int *inputPage, int inputPageLength, int *output, int outputLength) {
    printf("LRUwithMatrix :\n");
    int mat[MEMORYLENGTH][MEMORYLENGTH];
    memset(mat, 0, 4 * MEMORYLENGTH * MEMORYLENGTH);
    int count = 0;
    for (int i = 0; i < inputPageLength; ++i) {
        matrixPush(inputPage[i], &count, output, outputLength, mat);
        printPageArray(output, outputLength);
        printMateix(mat);
    }
}

void queuePushSecondChance(int page, int *count, int *array, int arrayLength, int *markedArray) {
    for (size_t i = 0; i < *count; i++) {
        if (array[i] == page) {
            if (markedArray[i] == 1) {
                for(int j = i ; j >= 1 ; --j) {
                    array[j] = array[j-1];
                    markedArray[j] = markedArray[j-1];
                }
                array[0] = page;
                markedArray[0] = 0;
            } else { 
                markedArray[i] = 1;
            }
            return;
        }
    }

    if (arrayLength <= 0) {
        printf("The array length is null！ \n");
        return;
    }

    if (*count != arrayLength) {
        for (int i = arrayLength - 1; i >= 1; --i) {
            array[i] = array[i - 1];
            markedArray[i] = markedArray[i - 1];
        }
        array[0] = page;
        (*count)++;
    }
    else {
        if (arrayLength == 1) {
            array[0] = page;
            return;
        }

        for (int i = arrayLength - 1; i >= 1; --i) {
            array[i] = array[i - 1];
            markedArray[i] = markedArray[i-1];
        }
        array[0] = page;
    }
}

void SecondChance(int *inputPage, int inputPageLength, int *output, int outputLength) {

    printf("SecondChance :\n");
    int count = 0;
    int markedArray[MEMORYLENGTH];
    memset(markedArray, 0, 4 * MEMORYLENGTH);
    for (int i = 0; i < inputPageLength; ++i) {
        queuePushSecondChance(inputPage[i], &count, output, outputLength, markedArray);
        printPageArray(output, outputLength);
        printf("Mark Array: ");
        printPageArray(markedArray, MEMORYLENGTH);
    }
}

int main(int argc, char const *argv[])
{
    int inputPage[] = {7, 8, 1, 2, 0, 3, 5, 4, 2, 6, 9, 7, 5, 1, 2, 0, 8, 7, 1, 0};

    int memory[MEMORYLENGTH] = {-1, -1, -1, -1, -1};

    printf("inputPage: ");
    printPageArray(inputPage, 20);
    // FIFO(inputPage, 20, memory, MEMORYLENGTH);
    // LRUwithStack(inputPage, 20, memory, MEMORYLENGTH);
    // LRUwithMatrix(inputPage, 20, memory, MEMORYLENGTH);
    SecondChance(inputPage, 20, memory, MEMORYLENGTH);
    
    return 0;
}